SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Enumeration algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Enumeration algorithm</span></span>

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><p>In <a href="Computer_science" title="Computer science">computer science</a>, an <b>enumeration algorithm</b> is an <a href="Algorithm" title="Algorithm">algorithm</a> that <a href="Enumeration" title="Enumeration">enumerates</a> the answers to a <a href="Computational_problem" title="Computational problem">computational problem</a>. Formally, such an algorithm applies to problems that take an input and produce a list of solutions, similarly to <a href="Function_problems" class="mw-redirect" title="Function problems">function problems</a>. For each input, the enumeration algorithm must produce the list of all solutions, without duplicates, and then halt. The performance of an enumeration algorithm is measured in terms of the time required to produce the solutions, either in terms of the <b>total time</b> required to produce all solutions, or in terms of the maximal <b>delay</b> between two consecutive solutions and in terms of a <b>preprocessing</b> time, counted as the time before outputting the first solution. This complexity can be expressed in terms of the size of the input, the size of each individual output, or the total size of the set of all outputs, similarly to what is done with <a href="Output-sensitive_algorithm" title="Output-sensitive algorithm">output-sensitive algorithms</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Formal_definitions">Formal definitions</h2></div>

<p>An enumeration problem <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math></span><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"></span> is defined as a relation <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R}</annotation>

</semantics>

</math></span><img src="./4b0bfb3769bf24d80e15374dc37b0441e2616e33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.764ex; height:2.176ex;" alt="{\displaystyle R}" loading="lazy"></span> over <a href="String_(computer_science)" title="String (computer science)">strings</a> of an arbitrary <a href="Alphabet_(computer_science)" class="mw-redirect" title="Alphabet (computer science)">alphabet</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma }</annotation>

</semantics>

</math></span><img src="./9e1f558f53cda207614abdf90162266c70bc5c1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \Sigma }" loading="lazy"></span>:

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R\subseteq \Sigma ^{*}\times \Sigma ^{*}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R\subseteq \Sigma ^{*}\times \Sigma ^{*}}</annotation>

</semantics>

</math></span><img src="./a53c83357aa1c3631c415182a64259fc01b180e5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:13.167ex; height:2.509ex;" alt="{\displaystyle R\subseteq \Sigma ^{*}\times \Sigma ^{*}}" loading="lazy"></span>

</p><p>An algorithm solves <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math></span><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"></span> if for every input <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math></span><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"></span> the algorithm produces the (possibly infinite) sequence <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math></span><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"></span> such that <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math></span><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"></span> has no duplicate and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z\in y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z\in y}</annotation>

</semantics>

</math></span><img src="./1e6c1daf2edbddd3accbda2eb55e90517fa623be.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.084ex; height:2.176ex;" alt="{\displaystyle z\in y}" loading="lazy"></span> if and only if <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (x,z)\in R}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (x,z)\in R}</annotation>

</semantics>

</math></span><img src="./2973d160a5ae6f7de2ad746e018ebd00d4a5adb5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.866ex; height:2.843ex;" alt="{\displaystyle (x,z)\in R}" loading="lazy"></span>. The algorithm should halt if the sequence <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</p>

<div class="mw-heading mw-heading2"><h2 id="Common_complexity_classes">Common complexity classes</h2></div>

<p>Enumeration problems have been studied in the context of <a href="Computational_complexity_theory" title="Computational complexity theory">computational complexity theory</a>, and several <a href="Complexity_class" title="Complexity class">complexity classes</a> have been introduced for such problems.

</p><p>A very general such class is <b>EnumP</b>,<sup id="cite_ref-closure_1-0" class="reference"><a href="#cite_note-closure-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> the class of problems for which the correctness of a possible output can be checked in <a href="Polynomial_time" class="mw-redirect" title="Polynomial time">polynomial time</a> in the input and output. Formally, for such a problem, there must exist an algorithm A which takes as input the problem input <i>x</i>, the candidate output <i>y</i>, and solves the <a href="Decision_problem" title="Decision problem">decision problem</a> of whether <i>y</i> is a correct output for the input <i>x</i>, in polynomial time in <i>x</i> and <i>y</i>. For instance, this class contains all problems that amount to enumerating the <a href="Witness_(mathematics)" title="Witness (mathematics)">witnesses</a> of a problem in the <a href="Class_(complexity_theory)" class="mw-redirect" title="Class (complexity theory)">class</a> <a href="NP_(complexity)" title="NP (complexity)">NP</a>.

</p><p>Other classes that have been defined include the following. In the case of problems that are also in <b>EnumP</b>, these problems are ordered from least to most specific:

</p>

<ul><li><b>Output polynomial</b>, the class of problems whose complete output can be computed in polynomial time.</li>

<li><b>Incremental polynomial time</b>, the class of problems where, for all <i>i</i>, the <i>i</i>-th output can be produced in polynomial time in the input size and in the number <i>i</i>.</li>

<li><b><a href="Polynomial_delay" title="Polynomial delay">Polynomial delay</a></b>, the class of problems where the delay between two consecutive outputs is polynomial in the input (and independent from the output).</li>

<li><b>Strongly polynomial delay</b>, the class of problems where the delay before each output is polynomial in the size of this specific output (and independent from the input or from the other outputs). The preprocessing is generally assumed to be polynomial.</li>

<li><b>Constant delay</b>, the class of problems where the delay before each output is constant, i.e., independent from the input and output. The preprocessing phase is generally assumed to be polynomial in the input.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Common_techniques">Common techniques</h2></div>

<ul><li><b><a href="Backtracking" title="Backtracking">Backtracking</a></b>: The simplest way to enumerate all solutions is by systematically exploring the space of possible results (<a href="Partition_(mathematics)" class="mw-redirect" title="Partition (mathematics)">partitioning</a> it at each successive step).<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> However, performing this may not give good guarantees on the delay, i.e., a backtracking algorithm may spend a long time exploring parts of the space of possible results that do not give rise to a full solution.</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output .vanchor>:target~.vanchor-text{background-color:#b1d2ff}@media screen{html.skin-theme-clientpref-night .mw-parser-output .vanchor>:target~.vanchor-text{background-color:#0f4dc9}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .vanchor>:target~.vanchor-text{background-color:#0f4dc9}}

/* end https://en.wikipedia.org/ */

</style><span class="vanchor"><span class="vanchor-text">Flashlight search</span></span></b>: This technique improves on backtracking by exploring the space of all possible solutions but solving at each step the problem of whether the current partial solution can be extended to a partial solution.<sup id="cite_ref-closure_1-1" class="reference"><a href="#cite_note-closure-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> If the answer is no, then the algorithm can immediately backtrack and avoid wasting time, which makes it easier to show guarantees on the delay between any two complete solutions. In particular, this technique applies well to <a href="Self-reducible" class="mw-redirect" title="Self-reducible">self-reducible</a> problems.</li>

<li><b>Closure under set operations</b>: If we wish to enumerate the disjoint <a href="Union_(set_theory)" title="Union (set theory)">union</a> of two sets, then we can solve the problem by enumerating the first set and then the second set. If the union is non disjoint but the sets can be enumerated in <a href="Sorting" title="Sorting">sorted order</a>, then the enumeration can be performed in parallel on both sets while eliminating duplicates on the fly. If the union is not disjoint and both sets are not sorted then duplicates can be eliminated at the expense of a higher memory usage, e.g., using a <a href="Hash_table" title="Hash table">hash table</a>. Likewise, the <a href="Cartesian_product" title="Cartesian product">cartesian product</a> of two sets can be enumerated efficiently by enumerating one set and joining each result with all results obtained when enumerating the second step.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Examples_of_enumeration_problems">Examples of enumeration problems</h2></div>

<ul><li>The <a href="Vertex_enumeration_problem" title="Vertex enumeration problem">vertex enumeration problem</a>, where we are given a <a href="Polytope" title="Polytope">polytope</a> described as a <a href="System_of_equations" title="System of equations">system</a> of <a href="Linear_inequality" title="Linear inequality">linear inequalities</a> and we must enumerate the <a href="Vertex_(geometry)" title="Vertex (geometry)">vertices</a> of the polytope.</li>

<li>Enumerating the minimal transversals of a <a href="Hypergraph_(mathematics)" class="mw-redirect" title="Hypergraph (mathematics)">hypergraph</a>. This problem is related to <a href="Monotone_dualization" title="Monotone dualization">monotone dualization</a> and is connected to many applications in <a href="Database_theory" title="Database theory">database theory</a> and <a href="Graph_theory" title="Graph theory">graph theory</a>.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup></li>

<li>Enumerating the answers to a <a href="Database_query" class="mw-redirect" title="Database query">database query</a>, for instance a <a href="Conjunctive_query" title="Conjunctive query">conjunctive query</a> or a query expressed in <a href="Monadic_second-order" class="mw-redirect" title="Monadic second-order">monadic second-order</a>. There have been characterizations in <a href="Database_theory" title="Database theory">database theory</a> of which conjunctive queries could be enumerated with <a href="Linear_time" class="mw-redirect" title="Linear time">linear</a> preprocessing and <a href="Constant_time" class="mw-redirect" title="Constant time">constant</a> delay.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup></li>

<li>The problem of <a href="Clique_problem#Listing_all_maximal_cliques" title="Clique problem">enumerating maximal cliques</a> in an input graph, e.g., with the <a href="Bron%E2%80%93Kerbosch_algorithm" title="Bron–Kerbosch algorithm">Bron–Kerbosch algorithm</a></li>

<li>Listing all elements of structures such as <a href="Matroid" title="Matroid">matroids</a> and <a href="Greedoid" title="Greedoid">greedoids</a></li>

<li>Several problems on graphs, e.g., enumerating <a href="Independent_set_(graph_theory)" title="Independent set (graph theory)">independent sets</a>, <a href="Path_(graph_theory)" title="Path (graph theory)">paths</a>, <a href="Cut_(graph_theory)" title="Cut (graph theory)">cuts</a>, etc.</li>

<li>Enumerating the <a href="Boolean_satisfiability_problem" title="Boolean satisfiability problem">satisfying assignments</a> of representations of <a href="Boolean_function" title="Boolean function">Boolean functions</a>, e.g., a Boolean formula written in <a href="Conjunctive_normal_form" title="Conjunctive normal form">conjunctive normal form</a> or <a href="Disjunctive_normal_form" title="Disjunctive normal form">disjunctive normal form</a>, a <a href="Binary_decision_diagram" title="Binary decision diagram">binary decision diagram</a> such as an <a href="OBDD" class="mw-redirect" title="OBDD">OBDD</a>, or a <a href="Boolean_circuit" title="Boolean circuit">Boolean circuit</a> in restricted classes studied in <a href="Knowledge_compilation" title="Knowledge compilation">knowledge compilation</a>, e.g., <a href="Negation_normal_form" title="Negation normal form">NNF</a>.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Connection_to_computability_theory">Connection to computability theory</h2></div>

<p>The notion of enumeration algorithms is also used in the field of <a href="Computability_theory" title="Computability theory">computability theory</a> to define some high complexity classes such as <b><a href="RE_(complexity)" title="RE (complexity)">RE</a></b>, the class of all <a href="Recursively_enumerable" class="mw-redirect" title="Recursively enumerable">recursively enumerable</a> problems. This is the class of sets for which there exist an enumeration algorithm that will produce all elements of the set: the algorithm may run forever if the set is infinite, but each solution must be produced by the algorithm after a finite time.

</p>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFStrozeckiMary2019" class="citation journal cs1">Strozecki, Yann; Mary, Arnaud (2019). <a rel="nofollow" class="external text" href="https://dmtcs.episciences.org/5549">"Efficient Enumeration of Solutions Produced by Closure Operations"</a>. <i>Discrete Mathematics & Theoretical Computer Science</i>. <b>21</b> (3). <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1712.03714">1712.03714</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.23638%2FDMTCS-21-3-22">10.23638/DMTCS-21-3-22</a>.</cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite id="CITEREFReadTarjan1975" class="citation journal cs1"><a href="Ronald_C._Read" title="Ronald C. Read">Read, Ronald C.</a>; <a href="Robert_Tarjan" title="Robert Tarjan">Tarjan, Robert E.</a> (1975). <span class="id-lock-subscription" title="Paid subscription required"><a rel="nofollow" class="external text" href="https://onlinelibrary.wiley.com/doi/10.1002/net.1975.5.3.237">"Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees"</a></span>. <i>Networks</i>. <b>5</b> (3): <span class="nowrap">237–</span>252. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2Fnet.1975.5.3.237">10.1002/net.1975.5.3.237</a>.</cite></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite id="CITEREFHagen2008" class="citation book cs1">Hagen, Matthias (2008). <a rel="nofollow" class="external text" href="https://cuvillier.de/de/shop/publications/1237"><i>Algorithmic and Computational Complexity Issues of MONET</i></a>. Göttingen: Cuvillier. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9783736928268</bdi>.</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFBaganDurandGrandjean2007" class="citation journal cs1">Bagan, Guillaume; Durand, Arnaud; Grandjean, Etienne (2007). Duparc, Jacques; Henzinger, Thomas A. (eds.). "On Acyclic Conjunctive Queries and Constant Delay Enumeration". <i>Computer Science Logic</i>. Lecture Notes in Computer Science. <b>4646</b>. Springer Berlin Heidelberg: <span class="nowrap">208–</span>222. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-74915-8_18">10.1007/978-3-540-74915-8_18</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9783540749158</bdi>.</cite></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite id="CITEREFMarquisDarwiche2002" class="citation journal cs1">Marquis, P.; Darwiche, A. (2002). "A Knowledge Compilation Map". <i>Journal of Artificial Intelligence Research</i>. <b>17</b>: <span class="nowrap">229–</span>264. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1106.1819">1106.1819</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1613%2Fjair.989">10.1613/jair.989</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:9919794">9919794</a>.</cite></span>

</li>

</ol></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-24" href="https://en.wikipedia.org/wiki/?title=Enumeration_algorithm&oldid=1297105022">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>